#include "binaryTree.h"
/*
 *Find item x in the tree.
 *Return the matching item or ITEM_NOT_FOUND if not found
 */
template <class Compareable>
const Compareable & BinarySearchTree<Compareable>::
find(const Compareable &x) const
{
	return elementAt(find(x, root));
}

/*
 *Internal method to get element data member in node t.
 *Return the element data member or ITEM_NOT_FOUND if t is NULL
 */
template <class Compareable>
const Compareable & BinarySearchTree<Compareable>::
elementAt(BinaryNode<Compareable> *t) const
{
	return t == NULL ? ITEM_NOT_FOUND: t->element;
}

/*
 *Internal method to find an item in a subtree.
 *x is item to search for.
 *t is the node that roots the tree.
 *Return node containing the matched item.
 */
template <class Compareable>
BinaryNode<Compareable> * 
BinarySearchTree<Compareable>::
find(const Compareable &x, BinaryNode<Compareable> *t) const
{
	if (t == NULL)
		return NULL;
	else if (x < t->element)
		return find(x, t->left);
	else if (x > t->element)
		return find(x, t->right);
	else
		return t;
}

/*
 *Internal method to find the smallest item in a subtree t.
 *Return node containing the smallest item.
 */
template <class Compareable>
BinaryNode<Compareable> *
BinarySearchTree<Compareable>::findMin(BinaryNode<Compareable> *t) const
{
	if (t == NULL)
		return NULL;
	if (t->left == NULL)
		return t;
	return findMin(t->left);
}

/*
 *Internal method to find the largest item in a subtree t.
 *Return node containing the largest item.
 */
template <class Compareable>
BinaryNode<Compareable> *
BinarySearchTree<Compareable>::findMax(BinaryNode<Compareable> *t) const
{
	if (t != NULL)
		while (t->right != NULL)
			t = t->right;
	return t;
}

/*
 *Internal method to insert into a subtree.
 *x is the item to insert.
 *t is the node that roots the tree.
 *set the new root.
 */
template <class Compareable>
void BinarySearchTree<Compareable>::
insert(const Compareable &x, BinaryNode<Compareable> * &t) const
{
	if (t == NULL)
		t = new BinaryNode<Compareable>(x, NULL, NULL);
	else if (x < t->element)
		insert(x, t->left);
	else if (x > t->element)
		insert(x, t->right);
	else
		;
}

/*
 *Internal method to remove from a subtree.
 *x is the item to remove.
 *t is the node that roots the tree.
 *set the new root.
 */
template <class Compareable>
void BinarySearchTree<Compareable>::
remove(const Compareable &x, BinaryNode<Compareable> * &t) const
{
	if (t == NULL)
		return;
	if (x < t->element)
		remove(x, t->left);
	else if (x > t->element)
		remove(x, t->right);
	else if (t->left != NULL & t->right != NULL) {
		t->element = findMin(t->right)->element;
		remove(x, t->right);
	} 
	else {
		BinaryNode<Compareable> *oldNode = t;
		t = (t->left != NULL) ? t->left : t->right;
		delete oldNode;
	}
}

/*
 *Destructor for the tre
 */
template <class Compareable>
BinarySearchTree<Compareable>::~BinarySearchTree()
{
	makeEmpty();
}

/*
 *Internal method to make subtree empty.
 */
template <class Compareable>
void BinarySearchTree<Compareable>::
makeEmpty(BinaryNode<Compareable> * &t) const
{
	if (t != NULL) {
		makeEmpty(t->left);	
		makeEmpty(t->right);
		delete t;
	}
	t = NULL;
}

/*
 *Deep copy.
 */
template <class Compareable>
const BinarySearchTree<Compareable> &
BinarySearchTree<Compareable>::
operator=(const BinarySearchTree<Compareable> &rhs)
{
	if (this != &rhs) {
		makeEmpty();
		root = clone(rhs.root);
	}
	return *this;
}

/*
 *Internal method to clone subtree.
 */
template <class Compareable>
BinaryNode<Compareable> *
BinarySearchTree<Compareable>::clone(BinaryNode<Compareable> *t) const 
{
	if (t == NULL)
		return NULL;
	else 
		return new BinaryNode<Compareable>(t->element, clone(t->left), 
		                                               clone(t->right));
}
